package leetcode.editor.cn.dsa20_heap;
//给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
// 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
// 找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。

import java.util.*;

public class FindKPairsWithSmallestSums373_1 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> result = new ArrayList<>();
            if (nums1.length == 0 || nums2.length == 0) return result;
            // 优先队列默认是小顶堆，通过传入比较规则实现大顶堆
            PriorityQueue<List<Integer>> queue = new PriorityQueue<>(k, (o1, o2) -> {
                return o2.get(0) + o2.get(1) - o1.get(0) - o1.get(1);
            });
            for (int i = 0; i < Math.min(nums1.length, k); i++) {
                for (int j = 0; j < Math.min(nums2.length, k); j++) {
                    // 如果最大堆未满或者当前数组和比堆顶的数组和小，加入最大堆
                    if (queue.size() != k || nums1[i] + nums2[j] < queue.peek().get(0) + queue.peek().get(1)) {
                        if (queue.size() == k) queue.poll(); // 满了先删除堆顶元素
                        List<Integer> pair = new ArrayList<>();
                        pair.add(nums1[i]);
                        pair.add(nums2[j]);
                        queue.add(pair);
                    }
                }
            }
            // 元素依次出队，倒序插入数组即可
            while (!queue.isEmpty()) {
                // 每次出队堆顶元素会自动进行调整，保证当前堆顶仍然是最大值
                result.add(0, queue.poll());
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}